package com.mars.algorithm;

/**
 * @Author King
 * @create 2020/8/18 10:21
 */
public class ListNodeCollection {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode tail = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmpNode = cur.next;
            cur.next = tail;
            tail = cur;
            cur = tmpNode;
        }
        return tail;
    }

    public static void main(String[] args) {
        int[] target = new int[]{10527, 740, 9013, 1300, 29680, 4898, 13993, 15213, 18182, 24254, 3966, 24378, 11522, 9190, 6389, 32067, 21464, 7115, 7760, 3925, 31608, 16047, 20117, 239, 14254, 3647, 11664, 27710, 2374, 23076, 5655, 9035, 4725, 13013, 12690, 22900, 27252, 32431, 2234, 281, 21614, 25927, 4512, 12695, 23964, 1279, 24305, 10618, 9903, 9943, 21625, 16622, 23662, 25734, 1255, 24695, 9120, 29898, 7376, 20450, 31788, 4604, 32502, 29052, 24447, 12007, 30153, 15745, 7726, 28122, 7726, 4567, 16604, 3580, 28544, 10748, 28767, 17120, 1236, 21310, 10526, 10841, 2946, 12586, 15805, 21648, 31457, 9798, 27901, 4691, 31057, 13571, 3805, 32176, 4735, 27885, 7430, 28867, 8932, 14373, 6757, 24268, 7311, 7441, 7706, 17284, 2341, 18514, 1425, 7346, 27942, 29430, 4590, 8697, 28785, 30959, 29871, 12020, 28683, 13252, 3980, 4997, 23836, 28039, 27554, 15977, 3386, 7, 11217, 30224, 24554, 29766, 32355, 5036, 23908, 13870, 20974, 29833, 12951, 12415, 20859, 5532, 11885, 25868, 27623, 3422, 9296, 21799, 27274, 22491, 22509, 20058, 23319, 10501, 22072, 28504, 20675, 14671, 24496, 31026, 16554, 16503, 18404, 16590, 32110, 4771, 28214, 21654, 5665, 5040, 13279, 10861, 7269, 29895, 4915, 27111, 5585, 28721, 15398, 9913, 7319, 30572, 23056, 8046, 29540, 1918, 26285, 21596, 4232, 6025, 11880, 2775, 25687, 21920, 27097, 4260, 24271, 9689, 4236, 21424, 30843, 6051, 18692, 8706, 17046, 17754, 6655, 9711, 17012, 21017, 16636, 29325, 7198, 31184, 20987, 13418, 20541, 26518, 1156, 23165, 4409, 17984, 20970, 19292, 29601, 16178, 18641, 31408, 32206, 23413, 14830, 29414, 23235, 31498, 8718, 10024, 13400, 22142, 30042, 8588, 30872, 16063, 12249, 24971, 3687, 3886, 20278, 32436, 15720, 1525, 6596, 25505, 19741, 30363, 22207, 13611, 8016, 2774, 23509, 14810, 18866, 1440, 5092, 21919, 29379, 15500, 25350, 28102, 30193, 15195, 3019, 18726, 4868, 17866, 31173, 16539, 11449, 11183, 5450, 21430, 23213, 9028, 1141, 30130, 21117, 7619, 32110, 9898, 27692, 18995, 3563, 11530, 17861, 14977, 31735, 836, 19009, 24274, 9203, 19908, 8106, 19224, 30682, 27941, 16513, 31459, 969, 165, 17502, 1915, 7102, 27862, 7126, 1067, 5791, 14999, 17313, 29919, 14975, 25155, 13052, 4850, 15902, 22312, 2381, 21569, 942, 26427, 16134, 26756, 28893, 17161, 24011, 8414, 2063, 16881, 983, 30130, 9963, 13969, 13980, 7865, 3610, 26494, 18601, 29009, 5707, 56, 22225, 31000, 13947, 3677, 8330, 32442, 16243, 24348, 16275, 28935, 28818, 20717, 730, 25673, 18892, 28031, 28828, 7124, 16115, 24562, 13262, 20958, 12341, 6983, 30908, 12689, 19431, 17685, 31984, 14175, 15745, 14461, 22101, 27542, 19945, 13663, 13724, 11060, 22772, 4046, 10207, 29436, 15402, 29634, 7044, 24777, 8905, 4365, 11365, 24355, 21261, 17297, 31533, 12048, 24751, 2991, 5125, 17452, 26795, 27395, 10353, 9980, 14919, 31054, 8308, 20864, 4433, 17843, 18171, 14855, 17832, 22567, 5497, 71, 5118, 26403, 25294, 28845, 25563, 5531, 31085, 20978, 12005, 19764, 22718, 12527, 28000, 2226, 9665, 7858, 11249, 8879, 3829, 5329, 11943, 31891, 10104, 29694, 17723, 4544, 32111, 20700, 13463, 19213, 28584, 786, 22934, 9846, 1662, 10909, 26891, 1810, 21501, 8042, 28932, 16709, 8007, 32548, 32592, 14134, 24374, 19787, 4414, 6531, 18499, 22918, 12456, 8244, 29095, 24634, 25136, 20462, 21952, 6491, 18634, 8041, 12725, 10626, 8827, 4388, 2141, 10560, 608, 5464, 19549, 14003, 27633, 18474, 30097, 17750, 13191, 24612, 1454, 8221, 18460, 24806, 16421, 20930, 19026, 26137, 6474, 26457, 5303, 6821, 8373, 16683, 6472, 12324, 27368, 26049, 14388, 27286, 15923, 2879};
        int result = trap(target);
        System.out.println(result);
    }

    private static int trap(int[] height) {
        //递归
        if (len(height) <= 1) {
            return 0;
        }
        int start = -1;
        int end = -1;
        int total = 0;
        int[] tmp = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            if (height[i] > 1) {
                tmp[i] = height[i] - 1;
            }
            if (start == -1 && height[i] > 0) {
                start = i;
                continue;
            }
            if (start != -1 && end == -1 && height[i] > 0) {
                end = i;
                total = total + (end - start - 1);
                start = end;
                end = -1;
            }
        }
        return trap(tmp) + total;
    }


    private static int len(int[] height) {
        int tmp = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] > 0) {
                tmp++;
            }
        }
        return tmp;
    }


    public int backtrap(int left, int right, int[] height) {
        if (left >= right - 1) { //递归结束条件为数组的长度小于3，因为这个时候，数组间的接水量绝对为0
            return 0;
        } else {
            int sum = 0;   //当前子容器的总储水量

            int first, second; //高度最高和第二高所对应的的索引
            if (height[left] >= height[right]) {
                first = left;
                second = right;
            } else {
                first = right;
                second = left;
            }

            //迭代获取高度最高和第二高所对应的的索引
            for (int i = left + 1; i < right; i++) {
                if (height[i] > height[first]) {
                    second = first;
                    first = i;
                } else if (height[i] > height[second]) {
                    second = i;
                }
            }
            int l, r; //左边界索引和右边界索引，用于递归
            if (first > second) {
                l = second;
                r = first;
            } else {
                r = second;
                l = first;
            }
            // 计算当前第二高和最高柱子之间的储水量
            int h = height[second]; //容器储水面积由高度矮的柱子决定
            for (int i = l + 1; i < r; i++) {
                sum += h - height[i];
            }
            return sum + backtrap(left, l, height) + backtrap(r, right, height);
        }
    }

    public int trapp(int[] height) {
        return backtrap(0, height.length - 1, height);
    }


}
